package 数组.最小的K个数;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/3/22 14:48
 * @description:剑指offer
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        Integer[] array = {3,2,1,4};

        //前者减后者，从小到大排序；后者减前者，就是从大到小排序。
        /*Comparator<Integer> comparator = (o1, o2) -> o1 - o2;
        Arrays.sort(array,comparator);*/


        Arrays.sort(array);
        int[] leastNumbers = getLeastNumbers(array, 2);
        System.out.println(leastNumbers);
    }

    //冒泡排序的基本思想
    public static int[] getLeastNumbers2(int[] arr, int k) {
        for (int i = 0; i < k ; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j] < arr[j-1]){
                    int tmp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = tmp;
                }
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = arr[i];
        }
        return result;
    }


    //堆排序 理论上来说求前k个最小数使用堆排序最快
    public static int[] getLeastNumbers(Integer[] arr, int k) {
        int[] vec = new int[k];
        if (k == 0) { // 排除 0 的情况
            return vec;
        }
        //使用优先队列创建大顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((num1, num2) -> num2 - num1);
        //先构建一个大小为k的堆
        for (int i = 0; i < k; ++i) {
            queue.offer(arr[i]);
        }
        //利用堆自身调整的特性，如果堆顶元素大于新元素，就对堆进行调整。
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = queue.poll();
        }
        return vec;
    }
}
